package com.lizk.union_find;

/**
 * 并查集，解决连接问题
 * 网络中的两个节点是否相连？
 * 以数组存储数据，以链的形式表示是否相连
 * 1.用数组来存储每个节点
 * 2.每个节点都有一个parent，parent表示当前节点的父节点
 * 3.相同顶节点的节点为相连的节点
 * 4.已经是顶节点的节点的父节点是自己的索引
 * 5.当两个合并两个节点的时候，就是让一个节点的顶节点作为另一个节点顶节点的子节点
 * @author lizhikui
 * @date 2020/2/14 16:19
 */
public class UnionFindLink {
    public static class Node{
        int id;
        int parent;
    }

    Node[] nodes ;

    public UnionFindLink(int length){
        nodes = new Node[length];
        for (int i = 0; i < length; i++) {
            Node node = new Node();
            node.id = i ;
            node.parent = i;

            nodes[i] = node;
        }
    }

    private int find (int id){
        if (nodes[id].parent == id){
            return nodes[id].parent;
        }
        return find(nodes[id].parent);
    }

    public void union (int one,int two){
        if (isConn(one,two)){
            return;
        }
        int oneRootIndex = find(one);
        int twoRootIndex = find(two);
        Node oneRoot = nodes[oneRootIndex];
        Node twoRoot = nodes[twoRootIndex];

        oneRoot.parent = twoRoot.parent;
    }

    public boolean isConn(int one,int two){
        return find(one) == find(two);
    }

}
